public class AVLTree {
    public static void main(String[] args) {
        AVLTree avlTree = new AVLTree();
        avlTree.insert(5);
        avlTree.insert(3);
        avlTree.insert(4);
        avlTree.insert(1);
        avlTree.insert(2);
        avlTree.insert(0);
        System.out.println();
    }
    static class TreeNode{
        private int val ;
        private TreeNode left ;
        private TreeNode right ;
        private int bf ; // 平衡因子
        private TreeNode parent ;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    private TreeNode root ;

    // 插入
    public void insert(int val){
        TreeNode node = new TreeNode(val);
        if(this.root == null) {
            this.root = node;
            return;
        }
        TreeNode cur = root ;
        TreeNode parent = null ;
        while(cur != null){
            parent = cur ;
            if(val > cur.val){
                cur = cur.right ;
            }else if(val < cur.val){
                cur = cur.left ;
            }else{
                return;   // 重复结点不要
            }
        }
        if(val > parent.val){
            parent.right = node ;
            node.parent = parent ;
        }else{
            parent.left = node ;
            node.parent = parent;
        }
        // 从下往上 , 更新 平衡因子
        cur = node ;
        while(parent != null){
            if(cur == parent.right){   // 平衡因子 = 右高 - 左高
                parent.bf ++ ;
            }else{
                parent.bf -- ;
            }
            if( parent .bf == 0){    // 树已经平衡
                break;
            }else if (parent.bf == 1 || parent.bf == -1){   // 这个子数平衡, 但不代表父数平衡
              // 继续往上
                cur = parent ;
                parent = cur.parent ;
            }else{   // 该子树不平衡
                if(parent.bf == 2){   // 右数高了
                    if(cur.bf == 1){   // 新插入的节点在右侧
                        // 左旋, 将右边的节点移到左边
                      rotateLeft(parent);
                    }else {            // 新插入的节点在左侧
                        // 右左双选
                        rotateRL(parent);
                    }
                }else{    // 左树高了
                    if(cur.bf == 1){   // 新插入的节点在右侧
                        //先 左旋, 在右旋 ,左右双旋
                        rotateLR(parent);

                    }else {            // 新插入的节点在左侧
                        // 右旋 , 把左侧的结点移到右侧 ;
                        rotateRight(parent);

                    }
                }
                // 不平衡通过旋转之后, 平衡了
                break ;
            }
        }

    }
    // 右左双旋
    private void rotateRL(TreeNode parent) {
        TreeNode subR = parent.right ;
        TreeNode subRL = subR.left ;
        int bf = subRL.bf ;
        // 右旋subR
        rotateRight(subR);
       // 左旋 parent
        rotateLeft(parent);
        if(bf == 1){
            parent.bf = -1 ;
            subR.bf= 0 ;
            subRL.bf = 0 ;
        }else if(bf == -1){
            parent.bf = 0 ;
            subRL.bf = 0 ;
            subR.bf = 1 ;
        }
    }

    private void rotateLR(TreeNode parent) {
        TreeNode subL  = parent.left ;
        TreeNode subLR = subL.right ;
        int bf = subLR.bf ;
        // 先 左旋 subL
        rotateLeft(subL);
        //在右旋 parent
        rotateRight(parent);
        // 修改 parent , subL , subR的bf
        if(bf == -1){
            subLR.bf = 0 ;
            subL.bf = 0 ;
            parent.bf = 1 ;
        }else if(bf==1){
            subLR.bf = 0 ;
            subL.bf = -1 ;
            parent.bf = 0 ;
        }
    }

    // 右旋
    private void rotateRight(TreeNode parent) {
        TreeNode subL = parent.left ;
        TreeNode subLR = subL.right ;
        // parent 变成subL的右子 , subLR 变成parent的左子 ;
        parent.left = subLR ;
        if(subLR != null){
            subLR.parent = parent ;
        }
        if(this.root == parent){
            this.root = subL ;
            this.root.parent = null ;

        }else{
            TreeNode pParent = parent.parent ;
            if(parent == pParent.left){
                subL.parent = pParent ;
                pParent.left = subL;
            }else{
                subL.parent = pParent ;
                pParent.right = subL ;
            }
        }

        parent.parent = subL ;
        subL.right = parent ;
        parent.bf = 0 ;
        subL.bf = 0 ;
    }

    //左旋
    private void rotateLeft(TreeNode parent) {
        TreeNode subR = parent.right ;
        TreeNode subRL = subR.left ;
        // parent变成 subR的左子 , subRL 变成parent的右子
        parent.right = subRL ;
        if(subRL != null){
            subRL.parent = parent ;
        }
        if(parent == this.root){
            this.root = subR ;
            this.root.parent = null ;
        }else{
            TreeNode pParent = parent.parent ;
            if(parent == pParent.left){
                subR.parent = pParent ;
                pParent.left = subR;
            }else{
                subR.parent =  pParent ;
                pParent.right = subR;
            }
        }

        parent.parent = subR ;
        subR.left = parent ;
        //修改平衡因子
        parent.bf = 0 ;
        subR.bf = 0 ;
    }
}
